package 每日一题OJ;

import java.util.HashSet;
import java.util.Set;

/**
 * @author shy_black
 * @date 2019/8/20 23:09
 * @Description:
 */
public class _287_寻找重复数 {

    public int findDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int i = 0;
        for(int num : nums){
            if(set.contains(num))
                return num;
            set.add(num);
        }

        return -1;
    }
}

/**
 *

class Solution {
    //用快慢指针来写，
    //n+1个数的数组中，有1-n的数字，所有必定有一个数组重复
    //这时两个重复的数字就组成了一个环
    //1 3 4 2 5 6 8 7 9 5
    //我们用一个快慢指针来做，快慢指针第一次相遇，表示找到了数组的重复元素
    //然后用一个新的指针来指向元素首节点，和慢指针以相同速度一起走，
    //此时这两个指针必在入环处相遇

    public int findDuplicate(int[] nums) {
        int fast = nums[nums[0]];
        int slow = nums[0];
        while(fast != slow) {
            fast = nums[nums[fast]];
            slow = nums[slow];
        }
        fast = 0;
        while(fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
            if(fast == slow)
                // return nums[slow];
                return slow;
        }

        return -1;
    }
}
 */